/*
*
给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。

在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为 负数 ，则返回 -1 。

注意，取余是在得到最大积之后执行的。

示例 1：

输入：grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1 。
示例 2：

输入：grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
输出：8
解释：最大非负积对应的路径如图所示 (1 * 1 * -2 * -4 * 1 = 8)
示例 3：

输入：grid = [[1,3],[0,-4]]
输出：0
解释：最大非负积对应的路径如图所示 (1 * 0 * -4 = 0)

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 15
-4 <= grid[i][j] <= 4

  - @author ala
  - @date 2024-09-19 12:47
*/
package main

import "fmt"

func main() {
	//grid := [][]int{{1, -2, 1}, {1, -2, 1}, {3, -4, 1}}
	grid := [][]int{
		{-1, -2, -3},
		{-2, -3, -3},
		{-3, -3, -2}}

	fmt.Println(maxProductPath(grid))
}

func maxProductPath(grid [][]int) int {
	M, N := len(grid), len(grid[0])

	dp1, dp2 := make([][]int, M), make([][]int, M)
	for i := range dp1 {
		dp1[i] = make([]int, N)
		dp2[i] = make([]int, N)
	}
	dp1[0][0], dp2[0][0] = grid[0][0], grid[0][0]
	for i := 1; i < M; i++ {
		v := dp1[i-1][0] * grid[i][0]
		dp1[i][0], dp2[i][0] = v, v
	}
	for j := 1; j < N; j++ {
		v := dp1[0][j-1] * grid[0][j]
		dp1[0][j], dp2[0][j] = v, v
	}

	for i := 1; i < M; i++ {
		for j := 1; j < N; j++ {
			v := grid[i][j]
			if v > 0 {
				dp1[i][j] = max(dp1[i-1][j], dp1[i][j-1]) * v
				dp2[i][j] = min(dp2[i-1][j], dp2[i][j-1]) * v
			} else if v < 0 {
				dp1[i][j] = min(dp2[i-1][j], dp2[i][j-1]) * v
				dp2[i][j] = max(dp1[i-1][j], dp1[i][j-1]) * v
			} else {
				dp1[i][j], dp2[i][j] = 0, 0
			}
		}
	}

	if dp1[M-1][N-1] < 0 {
		return -1
	} else {
		return dp1[M-1][N-1] % MOD
	}
}

var MOD int = 1e9 + 7
